/**
 * @param {number[][]} roads
 * @param {number} seats
 * @return {number}
 */
var minimumFuelCost = function (roads, seats) {
  let ans = 0
  let mp1 = new Map()
  let vistedMp = new Map()
  vistedMp.set(0, true)
  let pathMap = new Map()
  if (roads.length === 0) return 0
  roads.forEach(road => {
    let [i, j] = road
    pushMap(mp1, i, j)
    pushMap(mp1, j, i)
  })

  function dfs(v, parent) {
    const children = pathMap.get(v)
    // 示例3的情况，无子节点直接返回
    if (!children) return 1

    let total = 1
    for (let i = 0; i < children.length; i++) {
      if (children[i] === parent) {
        continue
      }
      // 累加子节点为根的节点个数
      total += dfs(children[i], v)
    }

    // 当前节点0，不需要计算前往父节点的消耗油量
    if (v !== 0) {
      // 计算当前人数，需要多少辆车可以到达父节点，也就是消耗油量
      ans += Math.ceil(total / seats)
    }

    // 返回节点数
    return total
  }
  dfs(0, -1)
  // vister(0, mp1, vistedMp, pathMap)
  // res = seatCar(pathMap, seats)
  return ans
}
var vister = function (floor, map, vistedMp, pathMap, parent_floor) {
  let arr = map.get(floor)
  arr.forEach(item => {
    if (!vistedMp.has(item)) {
      vistedMp.set(item, true)
      if (pathMap.has(floor)) {
        pathMap.get(floor).arr.push(item)
      } else {
        let dep = 0
        if (floor !== 0) {
          dep = pathMap.get(parent_floor).dep + 1
        }
        pathMap.set(floor, {
          dep: dep,
          // parent: parent_floor,
          arr: [item],
          cur: floor
        })
      }
      vister(item, map, vistedMp, pathMap, floor)
    }
  })
}

var seatCar = function (pathMap, seats) {
  let seated = new Map()
  let res = 0
  // let tmpPath = Object.values(path).sort((a, b) => b.dep - a.dep)
  let tmpPath = Array.from(pathMap.values()).sort((a, b) => b.dep - a.dep)
  tmpPath.forEach(item => {
    let arr = [] //当前节点上每个车上所坐人数
    item.arr.forEach(inner => {
      if (seated.has(inner)) {
        arr.push(...seated.get(inner))
      } else {
        arr.push(1) //孩子坐车
      }
    })
    res += arr.length // 孩子到自己需要的油耗
    arr.sort((a, b) => b - a)
    if (arr.length == 0 || arr[arr.length - 1] >= seats) {
      arr.push(1) //自己坐车
    } else {
      arr[arr.length - 1] = arr[arr.length - 1] + 1 //自己坐车
      //汽车合并
      arr.sort((a, b) => b - a)
      let start = 0
      let end = arr.length - 1
      while (start < end) {
        if (arr[start] >= seats) {
          start += 1
        } else {
          let dif = seats - arr[start]
          if (dif >= arr[end]) {
            arr[start] += arr[end]
            arr[end] = 0
            end -= 1
          } else {
            arr[start] += dif
            arr[end] -= dif
            start += 1
          }
        }
      }
      arr = arr.filter(item => item > 0)
    }
    seated.set(item.cur, arr)
  })
  return res
}

var pushMap = function (mp, key, val) {
  if (mp.has(key)) {
    mp.get(key).push(val)
  } else {
    mp.set(key, [val])
  }
}
let roads = [
  [3, 1],
  [3, 2],
  [1, 0],
  [0, 4],
  [0, 5],
  [4, 6]
]
roads = [
  [0, 1],
  [0, 2],
  [1, 3],
  [1, 4]
]
roads = [
  [0, 1],
  [0, 2],
  [1, 3],
  [3, 4],
  [0, 5],
  [6, 3],
  [5, 7],
  [3, 8]
]
roads = [
  [1, 0],
  [1, 2],
  [0, 3],
  [4, 3],
  [5, 2],
  [4, 6],
  [1, 7],
  [8, 6],
  [9, 6],
  [1, 10],
  [6, 11],
  [1, 12],
  [13, 9],
  [4, 14],
  [3, 15],
  [2, 16],
  [5, 17],
  [3, 18],
  [6, 19],
  [6, 20],
  [21, 16],
  [18, 22],
  [0, 23],
  [24, 1],
  [25, 12],
  [26, 24],
  [9, 27],
  [28, 23],
  [29, 25],
  [6, 30],
  [31, 21],
  [32, 21],
  [33, 23],
  [19, 34],
  [5, 35],
  [36, 7],
  [25, 37],
  [0, 38],
  [1, 39],
  [6, 40],
  [41, 3]
]

let seats = 2
seats = 5
console.log(minimumFuelCost(roads, seats))
